7 Метод с въвеждане на изкуствени променливи (Методът на голямото М)
7.1 Симплекс калкулатор
Да разгледаме прост пример за оптимизационна задача, която може да бъде решена с помощта на симплекс алгоритъма. Нека имаме следната линейна програма, например за максимизиране на печалбата от производство два вида козунак (и двата вида изискват определени количества от два вида ресурси: брашно и захар):
\max z(x_1, x_2) = x_1 + 1.5x_2
при следните ограничения:
\begin{aligned} x_1 + 2x_2 &\le 10 \quad \text{брашно (кг.)} \\ x_1 + x_2 &\le 8 \quad \text{захар (кг.)} \\ x_1, x_2 &\ge 0 \end{aligned}
- Приведете задачата в стандартен вид (т.е. с равенства вместо неравенства).
- Решете задачата с помощта на симплекс алгоритъма. Използвайте графично представяне, за да илюстрирате стъпките на алгоритъма.
- Проверете решението си с помощта на симплекс калкулатор симплекс калкулатор - М.
Можете да използвате този шаблон или да проверите урок 6
7.2 Теоритична постановка
Базисно представяне
- Всяка базисна променлива участва точно в 1 ограничение с коефициент +1
- Само 1 базисна променлива във всяко ограничение
- Неотрицателни десни страни
| Системата от ограничения е в базисно представяне спрямо x_1, x_4, x_5: | Системата от ограничения не е в базисно представяне: |
|---|---|
| \begin{aligned} x_1 - x_2 + 2x_3 &= 1 \\ x_2 - x_3 + x_4 &= 2 \\ 2x_2 + x_3 + x_5 &= 1 \\ x_j &\ge 0, j = 1..5 \end{aligned} | \begin{aligned} -2x_1 - x_2 + x_4 &= 3 \\ x_1 - x_3 &= 1 \\ 3x_1 + x_3 + x_5 &= 4 \\ x_j &\ge 0, j = 1..5 \end{aligned} |
Методът
- Индексните оценки, в които M участва с положителен знак са положителни. Индексните оценки, в които M участва с отрицателен знак са отрицателни.
- След излизане на изкуствените променливи от базиса, не е необходимо да се пресмятат техните коефициенти в симплекс таблицата. Причината е, че след този момент индексните оценки на изкуствените променливи винаги ще заемат положителна стойност.
Възможни решения на М-задачата
- Ако М-задачата няма решение, тогава и каноничната задача няма решение.
- Нека 𝑥∗ е оптимален план на М-задачата. Ако изкуствените променливи в 𝑥∗ имат стойност 0, то останалите променливи задават оптималния план на каноничната задача.
- Нека 𝑥∗ е оптимален план на М-задачата. Ако съществува изкуствена променлива в плана 𝑥∗, която има положителна стойност, то тогава каноничната задача няма решение.
7.3 Обобщени стъпки
Стъпка 1: Формулиране на ЗЛП Дефинирайте математическия модел на задачата за линейно програмиране (ЗЛП), включващ целевата функция и системата от ограничителни условия.
Стъпка 2: Конструиране на стандартна форма Приведете задачата в стандартна форма чрез въвеждане на допълнителни (slack), излишни (surplus) и изкуствени (artificial) променливи в зависимост от вида на неравенствата в ограниченията.
Стъпка 3: Намиране на начално базисно допустимо решение (IBFS) Определете началното базисно допустимо решение, като съблюдавате критериите за неотрицателност и идентифицирате базисните и небазисните променливи.
Стъпка 4: Построяване на симплекс таблица Съставете симплекс таблицата, която ясно показва базисните и небазисните променливи, коефициентите на целевата функция и ограничителните условия, както и стойностите на десните страни на уравненията. Правилното конструиране е критично, тъй като същата структура ще се използва при всяка итерация.
Стъпка 5: Изчисляване на оценките в индексния ред Изчислете стойностите в редовете за нетна оценка (индексния ред), за да проверите оптималността на решението. В зависимост от целта (минимизация или максимизация), се избира влизащата небазисна променлива.
Стъпка 6: Избор на ключов ред Определете ключовия (пивотния) ред чрез намиране на отношението (ratio) между стойностите в десната страна и положителните коефициенти в избрания стълб. Избира се редът с минималното положително отношение. Този ред указва излизащата базисна променлива.
Стъпка 7: Извършване на елементарни преобразувания Приложете необходимите математически операции (метода на Жордан-Гаус) по такъв начин, че избраният стълб да се превърне в единичен стълб (с единица в пивотния елемент и нули в останалите клетки).
Стъпка 8: Проверка за оптималност на решението Проверете оптималността чрез стойностите в индексния ред. При максимизация оптималността е достигната, ако всички стойности са по-големи или равни на нула.
7.4 Задачи
7.4.1 Задача 1
Фирма произвежда три основни продукта (x_1, x_2, x_3) и управлява две спомагателни дейности (x_4, x_5). Целта е да се състави производствен план, който минимизира общите разходи, при спазване на конкретни технологични ограничения за ресурсите.
Технологични ограничения
Производственият процес е ограничен от наличността и капацитета на три ключови ресурса:
Ресурс А (Баланс на дейност x_4): Разликата между капацитета на спомагателната дейност x_4 и вложените ресурси за продукти x_1 и x_2 трябва да бъде точно 3 единици.
Ресурс B (Връзка между x_1 и x_3): Количеството на първия продукт трябва да бъде точно с една единица по-голямо от това на третия.
Ресурс C (Общ капацитет с x_5): Сумата от тройното количество на първия продукт, количеството на третия и капацитета на втората спомагателна дейност трябва да е точно 4 единици.
Условия за неотрицателност Тъй като количествата представляват физически продукти и дейности, те не могат да бъдат отрицателни стойности: x_j \ge 0, \quad j = 1, \dots, 5
\begin{gather*} z(x) = 2x_1 + 3x_2 - 3x_3 \to \min \\ -2x_1 - x_2 + x_4 = 3 \\ x_1 - x_3 = 1 \\ 3x_1 + x_3 + x_5 = 4 \end{gather*}
Каноничен вид на задачата:
-z(x) = -2x_1 - 3x_2 + 3x_3 \to \max
X: \begin{cases} -2x_1 - x_2 + x_4 = 3 \\ x_1 - x_3 = 1 \\ 3x_1 + x_3 + x_5 = 4 \\ x_j \ge 0, j = 1, \dots, 5 \end{cases}
М-задача:
z^M(x) = -2x_1 - 3x_2 + 3x_3 - \color{red}{Mx_6} \to \max
X: \begin{cases} -2x_1 - x_2 + \color{cyan}{x_4} = 3 \\ x_1 - x_3 + \color{red}{x_6} = 1 \\ 3x_1 + x_3 + \color{cyan}{x_5} = 4 \\ x_j \ge 0, j = 1, \dots, 6 \end{cases}
Начален опорен план на М-задачата:
x^{(1)} = (0 \quad 0 \quad 0 \quad 3 \quad 4 \quad 1)^T
Решение
| B | c_B | x_1 | x_2 | x_3 | x_4 | x_5 | x_6 | a_0 | Отн. |
|---|---|---|---|---|---|---|---|---|---|
| -2 | -3 | 3 | 0 | 0 | -M | 0 | |||
| x_4 | 0 | -2 | -1 | 0 | 1 | 0 | 0 | 3 | - |
| x_6 | -M | 1 | 0 | -1 | 0 | 0 | 1 | 1 | 1/1 |
| x_5 | 0 | 3 | 0 | 1 | 0 | 1 | 0 | 4 | 4/3 |
| \Delta | M+2 | 3 | M-3 | 0 | 0 | 0 | -M |
| B | c_B | x_1 | x_2 | x_3 | x_4 | x_5 | x_6 | a_0 | Отн. |
|---|---|---|---|---|---|---|---|---|---|
| x_4 | 0 | 0 | -1 | -2 | 1 | 0 | 5 | - | |
| x_1 | -2 | 1 | 0 | -1 | 0 | 0 | 1 | - | |
| x_5 | 0 | 0 | 0 | 4 | 0 | 1 | 1 | 1/4 | |
| \Delta | 0 | 3 | -1 | 0 | 0 | >0 | -2 |
| B | c_B | x_1 | x_2 | x_3 | x_4 | x_5 | x_6 | a_0 | Отн. |
|---|---|---|---|---|---|---|---|---|---|
| x_4 | 0 | 0 | -1 | 0 | 1 | 1/2 | 11/2 | ||
| x_1 | -2 | 1 | 0 | 0 | 0 | 1/4 | 5/4 | ||
| x_3 | 3 | 0 | 0 | 1 | 0 | 1/4 | 1/4 | ||
| \Delta | 0 | 3 | 0 | 0 | 1/4 | >0 | -7/4 |
7.4.2 Задача 2
Първоначална задача z(x) = -5x_1 + 2x_2 \to \min
X: \begin{cases} x_1 - x_2 \ge 2 \\ x_1 - 2x_2 \ge 0 \\ 2x_1 - x_2 \le 1 \\ x_1 \ge 0 \end{cases}
Каноничен вид на задачата: -z(x) = 5x_1 - 2x_2' + 2x_2'' \to \max
X: \begin{cases} x_1 - x_2' + x_2'' - x_3 = 2 \\ -x_1 + 2x_2' - 2x_2'' + x_4 = 0 \\ 2x_1 - x_2' + x_2'' + x_5 = 1 \\ x_j \ge 0, j = 1,3,4,5 \\ x_2' \ge 0, x_2'' \ge 0 \end{cases}
М-задача: z^M(x) = 5x_1 - 2x_2' + 2x_2'' - \color{red}{Mx_6} \to \max
X: \begin{cases} x_1 - x_2' + x_2'' - x_3 + \color{red}{x_6} = 2 \\ -x_1 + 2x_2' - 2x_2'' + \color{cyan}{x_4} = 0 \\ 2x_1 - x_2' + x_2'' + \color{cyan}{x_5} = 1 \\ x_j \ge 0, j = 1,3,4,5,6 \\ x_2' \ge 0, x_2'' \ge 0 \end{cases}
Начален опорен план на М-задачата: x^{(1)} = (0 \quad 0 \quad 0 \quad 0 \quad 0 \quad 1 \quad 2)^T
7.5 Задача
Пивоварна произвежда светло пиво и бира, като за производството използва зърно, хмел и малц. Налични са 40 паунда зърно, 30 паунда хмел и 40 паунда малц. Един барел светло пиво се продава за $40 и за производството му са необходими 1 паунд зърно, 1 паунд хмел и 2 паунда малц. Един барел бира се продава за $50 и за производството му са необходими 2 паунда зърно, 1 паунд хмел и 1 паунд малц. Пивоварната може да продаде цялото произведено количество светло пиво и бира.
7.5.1 теорема
Нека x_1, \dots, x_n са променливи на \alpha и x_{n+1}, \dots, x_{n+m} са допълнителни неотрицателни променливи за привеждане в каноничен вид \alpha' на задачата \alpha. Нека y_1, \dots, y_m са променливи на задачата \beta и y_{m+1}, \dots, y_{m+n} са допълнителни неотрицателни променливи за привеждане в каноничен вид \beta' на задачата \beta. Нека са известни оптималните планове на \alpha' и \beta' — x^* и y^*. Тогава:
y_i^* = \Delta_{n+i}, \quad i = 1, \dots, m y_{m+j}^* = \Delta_j, \quad j = 1, \dots, n
x_j^* = \Delta_{m+j}, \quad j = 1, \dots, n x_{n+i}^* = \Delta_i, \quad i = 1, \dots, m